package com.yangjiayu.algorithm.binary_search;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

public class Leetcode287 {

    public static void main(String[] args) {
        int[] nums = {1,3,4,2,2};
        Leetcode287 leetcode287 = new Leetcode287();
        System.out.println(leetcode287.findDuplicate6(nums));
    }

    //HashMap保存每个数出现的次数
    public int findDuplicate1(int[] nums) {
        int n = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++){
            if(map.containsKey(nums[i])){
                return nums[i];
            }
            map.put(nums[i],1);
        }
        return -1;
    }



    //方法三: HashSet
    public int findDuplicate3(int[] nums) {
        int n = nums.length;
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0; i < n; i++){
            if(set.contains(nums[i])){
                return nums[i];
            }
            set.add(nums[i]);
        }
        return -1;
    }

    //方法四: 先排序 然后找相邻的元素
    public int findDuplicate4(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        for(int i = 0; i < n-1; i++){//遇到跟后一个相同的就是重复元素
            if(nums[i] == nums[i+1]){
                return nums[i];
            }
        }
        return -1;
    }

    //方法五：二分查找，查找1~N的自然数序列，寻找target
    public int findDuplicate5(int[] nums) {
        //定义左右指针
        int left = 1, right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;

            // 对当前的mid计算count值
            int count = 0;
            for(int j=0; j<nums.length; j++){
                if(nums[j] <= mid){
                    count++;
                }
                //判断count和mid本身的大小关系
                if(count > mid){
                    right = mid ;
                }else{
                    left = mid + 1; //count 小于等于mid自身，说明mid比target小，左指针右移
                }
                //左右指针重合，返回结果找到target
                if(left == right){
                    return left;
                }
            }
        }
        return -1;
    }

    //方法六：快慢指针
    //把数组看成链表
    /*
   index 0 1 2 3 4 5 6
   value 3 6 1 4 6 6 2

   找到环
   弗洛伊德循环检测算法（龟兔赛跑）
   第一阶段
   1. 快慢指针，快指针每次移动两步，慢指针每次移动一步
   2. 快慢指针相遇，说明有环
   第二阶段
   3. 慢指针重新指向头结点，快指针不动
   4. 慢指针和快指针同时移动，相遇的点就是环的入口点
     */
    public int findDuplicate6(int[] nums) {
        //定义快慢指针
        int slow = 0,fast = 0;
        //1.寻找环内相遇点
        do {
            //快指针一次走两部，满指针一次走一步
            slow = nums[slow];
            fast = nums[nums[fast]];
        }while(slow != fast);

        //循环结束。slow,fast 相遇点就是环的入口点
        //2.寻找环的入口点
        int before = 0,after = slow;
        while(before != after){
            before = nums[before];
            after = nums[after];
        }
        //循环结束，相遇点就是环的入口点，也就是重复元素
        return before;
    }


}


















